package com.hash;

import java.util.*;

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class CloneGraph {
    public Node cloneGraph(Node node){
        if (node == null) return node;

        ArrayList<Node> nodes = getNodes(node);

        HashMap<Node, Node> mapping = new HashMap<>();
        for (Node n : nodes){
            mapping.put(n, new Node(n.val));
        }

        for (Node n : nodes){
            Node newNode = mapping.get(n);
            for (Node neighbor : n.neighbors){
                newNode.neighbors.add(mapping.get(neighbor));
            }
        }

        return mapping.get(node);
    }

    /**
     * 获取图的全部节点
     * @param node
     * @return
     */
    private ArrayList<Node> getNodes(Node node) {
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();
        queue.offer(node);
        set.add(node);

        while (!queue.isEmpty()){
            Node head = queue.poll();
            for (Node neighbor: head.neighbors){
                if (!set.contains(neighbor)){
                    set.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return new ArrayList<>(set);
    }
}
